public class Solution {
    public int rob(int[] nums) {

        int n=nums.length;
        //注意首位相连，第一个位置偷是，第2个位置与最后一个位置不能偷
        //第一个位置不偷时，（1，n-1）就是rob1   的情况
        return Math.max(nums[0]+rob1(nums,2,n-2),rob1(nums,1,n-1));

    }
    public int rob1(int[] nums,int left,int right){

        if(nums==null||nums.length==0){
            return 0;
        }
        if(left>right){
            //注意对传入的下标进行合法性校验
            return 0;
        }

        int n=nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        f[left]=nums[left];//初始化时需要注意nums[left] ，而不再是nums[0]
        g[left]=0;

        for(int i=left+1;i<=right;i++ ){
            f[i]=nums[i]+g[i-1];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[right],g[right]);
    }
}